//图中单源最短路
//https://www.luogu.com.cn/problem/P3371
//#include <iostream>
//#include <vector>
//#include <queue>
//#include <set>
//#include <climits>
//#include <cmath>
//using namespace std;
//const int N = 1e4 + 10;
//typedef pair<int, int> PII;
//const int err = 2147483647;
//
//
//int arr[N];			//存储最终结果
//bool check[N];		//检查是否走过
//vector<PII> dp[N];	//邻接表
//
//int main()
//{
//	ios::sync_with_stdio(false);
//	int n, m, s; cin >> n >> m >> s;
//	for (int i = 1; i <= m; i++)
//	{
//		int u, v, w; cin >> u >> v >> w;
//		//存边
//		dp[u].push_back(make_pair(v, w));
//	}
//
//	//初始化arr
//	for (int i = 0; i <= n; i++)
//	{
//		arr[i] = err;
//	}
//	arr[s] = 0;
//
//	for (int i = 0; i < n - 1; i++)
//	{
//		//扩展n - 1次
//		int min_pos = 0;
//		for (int i = 1; i <= n; i++)
//		{
//			//选出最小并且没有走过的点
//			if (!check[i] && arr[i] < arr[min_pos]) min_pos = i;
//		}
//
//		//标记该点走过并且开始扩展
//		check[min_pos] = true;
//		for (auto& e : dp[min_pos])
//		{
//			int end = e.first; int len = e.second;
//			if (arr[min_pos] + len < arr[end]) arr[end] = arr[min_pos] + len;
//		}
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		cout << arr[i] << " ";
//	}
//	return 0;
//}


//优先级队列优化版
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <climits>
#include <cmath>

using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
const int err = 0x3f3f3f3f;

int arr[N];			//存储最终结果
bool check[N];		//检查是否走过
vector<PII> dp[N];	//邻接表

class compare
{
public:
	int operator()(const PII& a, const PII& b)
	{
		return a.first > b.first;
	}
};

int main()
{
	ios::sync_with_stdio(false);
	int n, m, s; cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		//存边
		dp[u].push_back(make_pair(v, w));
	}

	//初始化arr
	for (int i = 0; i <= n; i++)
	{
		arr[i] = err;
	}
	arr[s] = 0;
	priority_queue<PII,vector<PII>,compare> que; //快速查找最小点
	que.push({ 0,s });

	while (que.size())
	{
		auto top = que.top(); que.pop();
		int u = top.second; int len = top.first;
		check[u] = true;
		for (const auto& e : dp[u])
		{
			int v = e.first; int w = e.second;
			if (!check[v] && arr[u] + w < arr[v])
			{
				arr[v] = arr[u] + w;
				que.push({ arr[v],v });
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		cout << arr[i] << " ";
	}
	return 0;
}